% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
% This document is distributed under Creative Commons Attribution-ShareAlike  %
% 3.0 Unported license. To see all the legal form of the license see          %
% http://creativecommons.org/licenses/by-sa/3.0/legalcode                     %
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
\documentclass[a4paper]{article}

\usepackage{graphicx}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{url}

\usepackage{fancyhdr}
\pagestyle{fancy}

\lhead{\sffamily A. Franco. \emph{An Analysis of Go Concurrency Model}}
\chead{}
\rhead{\includegraphics[width=17mm]{cc_sa}}
\lfoot{}
\cfoot{\thepage}
\rfoot{}

\usepackage{hyperref}
\hypersetup{
    colorlinks,%
    citecolor=black,%
    filecolor=black,%
    linkcolor=black,%
    urlcolor=black
}

\begin{document}

%--- LISTING SETTINGS ---------------------------------------------------------%
\definecolor{darkgray}{rgb}{0.97,0.97,0.95}
\definecolor{darkgreen}{rgb}{0.0, 0.6, 0.0}
\definecolor{gray}{rgb}{0.2,0.2,0.3}
\definecolor{fuchsia}{rgb}{0.6, 0.0, 0.95}
\definecolor{darkred}{rgb}{0.6, 0.0, 0.0}

\lstset{language=C++}
\lstset{backgroundcolor=\color{darkgray}}
\lstset{keywordstyle=\color{blue}\ttfamily}
\lstset{basicstyle=\color{gray}\ttfamily\footnotesize}
\lstset{commentstyle=\color{darkgreen}\ttfamily}
\lstset{morekeywords={go, package, func, type, var, import, interface, select, chan}}
\lstset{emph={int, int64, new, make, bool, int32}, emphstyle={\color{fuchsia}}}
\lstset{stringstyle=\color{darkred}}
\lstset{showstringspaces=false}
\lstset{numbers=left}
\lstset{numberstyle={\ttfamily\footnotesize}}
\lstset{firstnumber=last}
%------------------------------------------------------------------------------%

\title{
    An analysis of Go concurrency model\\
    \vspace{5mm}
    \includegraphics[width=4cm]{go_logo}
}
\author{Alberto Franco}
\date{Last revision \today}
\maketitle

\begin{abstract} 
    We are going to discuss a bit of the concurrency model that stands behind the
    Go programming language purposed by Google Inc. in 2008. After an analysis
    of its features we are going to discuss specifically choises of the 
    designer in supporting concurrency. It has been said that Go implements 
    ideas from Hoare's CSP\cite{hoare01} so we are going to overview CSP and 
    then analyze if it is implemented inside the language and how. If not we 
    will try ot understand if there are concurrency models that better describe
    Go. 
\end{abstract}

\section*{About this document}
This document is distributed under Creative Commons Attribution-ShareAlike 3.0
Unported License. You may redistribute and derive this work as long as you
share it with the same license. More details at 
\url{http://creativecommons.org/licenses/by-sa/3.0/}.

\section{Introduction}
Go has been matter of discussion over the last few months. It is the first try
after years by a big company to propose a new programming language of this kind.
It has been advertised as a panacea for big application programming due to its
light-weight syntax and its features in particular garbage-collection, 
concurrency and execution model. In this short report we will try to first give
an overview of the language and then dive deep into its concurrency model. 
The approach that will be followed is to present the features 
with some examples. A theorical
explanation is also gave to the reader. In the end we will present a complete
example of a complex concurrent application and we will try to draw some 
conclusions on the whole work done. 

\section{An overview of Go programming language}
The Go programming language does not deliver the usual object-oriented programming 
paradigm most of the programmers are used to. It is not like C++ or Java nor 
like old fashioned languages such as C or Pascal. It is something really new 
and sumarize years of research in the field in a simple but pretty way. 

\subsection{Execution model}
Go is definitely a compiled language, in the way C and C++ are. There is a 
compiler that take the sources and transforms it in an executable, no bytecodes
or such things just binaries dependant on the architecture and on the O/S.
This kind of execution model has been chosen in order to guarantee perfomance
to program written in Go since the language is tagged as ``System''\footnote{
    In Ousterhout's dichotomy a system programming language is statically tiped,
    compiled and it support the creation of large data structures. In layman's 
    terms such programming languages are performant enough to build with them 
    complex application such as servers, operating systems and other huge 
    systems perhaps.
}. It differs from C/C++ for many interesting aspects, mainly Go is garbage 
collect so programmer does not have to handle with memory release. This does not
limits the expressiveness of the language since memory is still usable at low 
level (as in C/C++) but with an easy mind because of the garbage collection. Go 
provides ``slices'' that are portion of memory that can be written and read but 
access is limited to the allocated area. Once program try to read an out of 
index byte a run-time error is raised.

\subsection{Types}
Type management is quite the new stuff. Go borrows some syntax from scripting 
language such as Python and Perl, it is not needed to declare the type of a 
variable but the compiler infers it from the initialization\footnote{
    Type inference in Go is not like is in ML or functional languages in 
    general. The initializing expression is evaluated and if it is not possible 
    to infer the type from the expression an error is raised.
} and the same is done for function return type.
There is not the classical type with classes as in C++ and Java there are
\emph{struct} and \emph{interface}. Structs are the definition of a aggregation 
of a certain amount of data and of some methods to operate on the data. There is
no keyword to define public and private data but the case of the first letter
of method (or field) name determinate if a method (or field) is public or 
private. It follows a simple example of the creation of a new type.
\begin{lstlisting}[frame=tb]
package main

import "fmt"

/// This is a public type, it is exported outside the package
type NewType struct {
    someInt int ///< Private field
    TheInt  int ///< Public field
}

/// Public method
func (self *NewType) SomeMethod int {
    return 3
}

func main() {
    var a *NewType = new(NewType) ///< No constructor
    fmt.Println(a.SomeMethod())   ///< Prints "3"
}
\end{lstlisting}
Interfaces are quite different and yet similar from those found in Java, they 
define a prototype for the implementation but a struct should not be marked 
explicitlly to implement an interface, it just need to implement the methods 
defined and the compiler infer that the interface has been implemented, once 
required. Let's see an example
\begin{lstlisting}[frame=tb]
/// A new interface definition
type NewInterface interface { 
    SomeMethod(int, int) ///< This is the method to implement
}

/// A new type not explicit marked to implement the inteface
type NewType struct {
    a int
}

/// Implementation of the method defined in the interface
func (self *NewType) SomeMethod(b, c int) {
    fmt.Println("Hello!")
}

/// This can be used with NewType
func UseInterface(ptr NewInterface) {
    ptr.SomeMethod(2, 3)
}

func main() {
    var a *NewType = new(NewType)
    UseInterface(a) ///< Prints "Hello!"
}
\end{lstlisting}

\subsection{Error handling}
The original language design did not provide an error recovering system. Errors
were originally handled just like in C, with the return of errors code in 
functions. At the present has been implemented what they call ``panic/recover''
system. It works differently from exceptions in C++ and Java to have a more
lightweight programming environment. When \texttt{panic} is called the execution 
is stoped (just like a \texttt{throw}) and the error go through the stack of 
callers until a \texttt{recover} is found. Seems identical to throw/catch 
mechanism but recover has not a specific role like catch statement but a generic
one, it may be assimilated to a \texttt{catch(...)} in C++.

\section{Go concurrency model and CSP}
Communicating Sequential Processes  is a formal language for describing 
concurrent systems. Let me name (in a 
FORTRAN fashion) CSP78 refering the calculus descibed in \cite{hoare01} and
CSP84 refering the one described in \cite{hoare02}. After a few examples and 
an analysis of Go semantics\cite{gospec} and a comparison with CSP\cite{roscoe01}
I came up with the fact that Go does implement CSP78 as a model of concurrency. 
The main difference between the two models are that CSP78 has not a solid 
theorical background. Tony Hoare itself states:
\emph{The most serious [problem of the article] is that fails to 
suggest any proof method to assist in the development and verification 
of correct problem}\cite{hoare01}. To overtake this problem a refinement of
the language has been done\cite{hoare02}. Go concurrency model 
has not a solid background if seen as CSP78. From the begining of my research 
it resemble much to another process calculus that has a more solid 
theorical background than CSP78, Milner's Calcus of Communicating 
Systems\cite{milner01}. That has the same structure of CSP78 but a more formal 
definition and verification framework. So we would like to say that Go 
concurrency model is, in the end, CCS but that is not true. Go does not have an
important feature that CCS has: non-deterministic choise (or sum), we will see 
how Go's guarded selection differs from CCS's sum.

\subsection{Go concurrency by examples} 
We will see how Go implements concurrency with a few examples to understand
deeply how the communications and the synchronizations happens. Examples are 
presented in growing difficulty order, the last is the one that uses more 
complex structures. First we are going to discuss a bit concurrency primitives 
and compare them with CCS.

\paragraph{Channel communication:} it is made possible thorugh the operator
\texttt{<-} that indicates which variable must be sent over which channel and 
viceversa.
\begin{lstlisting}[frame=tb]
    var channel chan int        ///< Declare a channel
    channel = make(chan int)    ///< Create the channel
    channel <- 1                ///< Send a variable to the channel
    var a int = <- channel      ///< Listen for comm on channel
\end{lstlisting}
Channel communications are asynchronous and one-to-one process. If process $A$ 
sends a message into channel $a$ and there are processes $B$ and $C$ listening
to the channel, message is delivered to the first between $B$ and $C$ that 
has started listening to the channel and then the message is consumed.

\paragraph{Guarded selection:} It may happens that you want to write a program
that reacts differently on the message received. This is made possible through
the guarded selection available in Go. 
\begin{lstlisting}[frame=tb]
    select {
        case i <- c:
            ...something...
        case c <- j:
            ...something different...
    }
\end{lstlisting}
It is the guarded selection Hoare speaks about in \cite{hoare01}. Expression in 
cases are evaluated top-to-bottom and the one that can be done is executed with 
his relative body, there is no fall throught. ``\emph{If multiple cases can proceed, a 
pseudo-random fair choice is made to decide which single communication will 
execute}''\cite{gospec}. If you look well at this structure you may see how it 
differs from CCS's sum: selection in Go is guarded so there is a condition to 
execute it and it is not non-deterministic.

\paragraph{Parallel composition:} the keyword \texttt{go} is available to 
create a concurrent flow of execution (as they call them \emph{goroutines}) that 
is not necessarily run on a different thread, the scheduler will manage 
which goroutines will go on which threads.
\begin{lstlisting}[frame=tb]
    go someFunc() ///< Starts a new goroutine
    /// It is possible to create on-the-fly a new function to start
    go func() {
        for {
            fmt.Println("Endless loop")
        }
    }()
\end{lstlisting}
Other construct of the concurrency model are easily obtained with language's 
features. For example restriction and renaming are just a the possibility to
have private data and to aggregate data structure and give some interfaces to
those.

\subsubsection{A classical problem: Dining Philosofers}
The most classical of concurrency problems is the Dining Philosofer 
problem\cite{dijkstra01}. Here is the description of the problem: 
\begin{center}
\begin{tabular}{p{11cm}}
``\emph{Five philosophers sit around a circular table. Each philosopher spends 
his life alternatively thinking and eating. In the centre of the table is a 
large plate of noodles. A philosopher needs two chopsticks to eat a helping of 
noodles. Unfortunately, as philosophy is not as well paid as computing, the 
philosophers can only afford five chopsticks. One chopstick is placed between 
each pair of philosophers and they agree that each will only use the chopstick 
to his immediate right and left}.''
\end{tabular}
\end{center}
This classical problem lead to deadlock when all philosofer take a fork on the 
same side, for example all take fork on their right side, there happen the 
deadlock. The following piece of code is the routine that each philofer perfom.
\begin{lstlisting}[frame=tb]
    /// Thinking routine. Think a random time in [0, 1sec]
    func (self *Philosofer) think () {
        fmt.Println(self.name + " is thinking...")
        time.Sleep(rand.Int63n(1000000))
    }

    /// The main routine of the philosofer.
    func (self *Philosofer) Routine() {
        for {
            self.think()
            /// Take right fork
            self.rightFork.Lock()
            fmt.Println("Right fork taken by " + self.name)
            
            /// Take left fork
            self.leftFork.Lock();
            fmt.Println(self.name + " is eating...")
            /// Release the forks
            self.rightFork.Unlock()
            self.leftFork.Unlock()
        }
    }
\end{lstlisting}
This is obviously prone to deadlock, if fact if we runs it we runs into 
deadlock. The nice thing is that Go run-time support identifies it and tell you 
a nice \texttt{throw: all goroutines are asleep - deadlock!} and then it prints 
all the stack trace from the goroutines\footnote{I am still using the term 
goroutine instead of thread because there is not a one-to-one mapping between
goroutines and threads as said before.}.

\subsubsection{A less classical problem: Barber Shop}
First example did not explaind much about Go concurrency we just used mutexes and
parallel composition, nothing strange. A pretty much interesting example is the 
barber shop one (this also came originally from Dijkstra):
\begin{center}
\begin{tabular}{p{11cm}}
``\emph{A barbershop consists of a waiting room with n chairs, and the
barber room containing the barber chair. If there are no customers
to be served, the barber goes to sleep. If a customer enters the
barbershop and all chairs are occupied, then the customer leaves
the shop. If the barber is busy, but chairs are available, then the
customer sits in one of the free chairs. If the barber is asleep, the
customer wakes up the barber. Write a program to coordinate the
barber and the customers.}''.
\end{tabular}
\end{center}
In our Go implementation we may use something more interesting such as channels. 
The way I thought to implement this is the following. I just put here the 
interesting functions not all the housekeeping done. 
\begin{lstlisting}[frame=tb]
    /// Barber serve all customers 
    func (self *Barber) Routine() {
        var customer *Customer
        for {
            /// Hold on for a customer
            customer = <- self.Chair
            /// Cut hair and wait a random time
            time.Sleep(rand.Int63n(1000))
            /// Notify the customer
            customer.CutHair <- 1
        }
    }
    
    /// Each customer enter the shop if the can he sits down
    func (self *Customer) EnterShop() {
        /// Enter shop and sit down
        mutex.Lock() 
        if customerCount == maxCustomers {
            fmt.Println(self.name, "exit")
            /// No room available, exit the shop
            mutex.Unlock()
            return
        }
        /// Sit down
        customerCount += 1
        mutex.Unlock()
        /// Awake the barber
        self.barber.Chair <- self
        // wait for the signal of the barber
        <- self.CutHair 
        self.getHairCut()
        /// Release the chair
        mutex.Lock(); 
        customerCount -= 1
        mutex.Unlock()
    }
\end{lstlisting}
As you can see in the code it is used the \texttt{<-} operator to exchange 
messages into the channels. 

\subsubsection{A simple TCP simulation}
Another example we present is a simple network protocol simulation. We 
want to implement a TCP simulator, without congestion window control, slow start
threshold management anfragile]d timeouts, just a simple protocol that sends a packet
and wait for an ack to come back to send again another packet. If ack is not
coming back because of an error resend the packet. Here is the code developed
for sender process.
\begin{lstlisting}[frame=tb]
    // Sender routine.
    func (self *Sender) SendData() {
        var packet int32
        var pktSent bool
        for {
            // Receive a packet
            packet = <- (*self.input)
            pktSent = false
            // Try to send it over the net
            for (!pktSent) {
                fmt.Println(self.name + " try to send a packet...")
                self.pktChan <- packet
                // Now made a choise depending if returns 
                // an ack or an error
                select {
                    case <- (*self.ackChan):
                        fmt.Println("Packet sent!")
                        pktSent = true
                    case <- (*self.errorChan):
                        fmt.Println("Error in pkt")
                }
            }
        }
    }
\end{lstlisting}
As you can see it is a pretty simple piece of code. One of the more interesting
stuff up here is the use of \texttt{select} statement. Depending on which 
channel receive a message the corresponding instructions are executed, this is 
a powerful statement, it has a more predicable behavior than non-deterministic 
sum of CCS although this concurrency model has no formal specification. In the
next few lines we will see how medium and receiver processes works.
\begin{lstlisting}[frame=tb]
    // Medium routine. Generate random errors. 
    func (self *Medium) Serve() {
        var packet int32
        for {
            /// Receive a packet
            packet = <- (*self.sendChan)
            if rand.Intn(100) > 50 {
                /// Generate random errors
                self.errorChan <- 1
            } else {
                self.transChan <- packet
            }
        }
    }
\end{lstlisting}
Medium is simple as it looks, receive message and delivers them only if no error
is generated else it returs to sender the error so it will resend message. 
Below there is receiver code that has no particular intelligence just takes 
messages and delivers to application layer. 
\begin{lstlisting}[frame=tb]
    // Receiver routine. Receives a message and delivers it 
    // to the application layer.
    func (self *Receiver) ReceiveData() {
        var packet int32
        for {
            /// Receive, deliver and ack
            packet = <- (*self.transChan)
            fmt.Println("Received pkt!")
            self.output <- packet
            self.ackChan <- 1
        }
    }
\end{lstlisting}

\subsection{$\pi$-calculus and Go}
Diving more deeply (but not that much) into concurrency theory $\pi$-calculus is
found. This calculus was introduced by Milner, Parrow and Walker to model 
mobile processes\cite{milner99}. Due to lacks of CCS it is not possible to model in those 
language changes of processes' communication capabilities, therefore this is
possible in this new calculus. In $\pi$-calculus a channel can be sent to 
another process and this exactly what can be done in Go. Channels in Go are
first class objects and they are really powerful, in fact, everything that is 
codable inside the language can be sent over channels. This is clearly done 
without any strange and complex concurrency model in mind but for sake of 
convenience, behind all those complex data structures and function passing
there are pointer that are sent over the channel and cleverly hidden behind
a strong type system. Language designers themselves claimed that they did not
try to make a formal language with lots of theoretical flavours but something 
usable and fast.

\subsubsection{Sending channels over channels}
The main advantage of $\pi$-calculus respect to CCS is the possibility to send
channels over channels. This is made available by Go's concurrency model. 
Follows a simple example of communication augmentation through channel passing.
\begin{lstlisting}[frame=tb]
func main() {
    ...
    go supportGoroutine(&chanOfChan)
    
    for i := 0; i < 10; i++ {
        myChan = make(chan int)
        chanOfChan <- myChan ///< Send the chan
        integer := <- myChan ///< Hold on for data
    }
}

/// Receive a commuication channel and send 
/// data over the channel received.
func supportGoroutine(channel *chan chan int) {
    var supportChan chan int
    for i := 0; i < 10; i++ {
        supportChan = <- (*channel) ///< Receive chan
        supportChan <- i ///< Send data over chan
    }
}
\end{lstlisting}

\subsubsection{Sending functions over channels}
We present a simple example on own a function can be sent over a channel, the 
following piece of code send a simple \texttt{func} onto our channel and the 
process that receives it just runs it. As you can see it is as easy as making 
channels that commuicates data.
\begin{lstlisting}[frame=tb]
func main() {
    var funcChannel chan func(int32)
    var callback func(int32)
    
    funcChannel = make (chan func(int32))
    go support(funcChannel)
    
    callback = <- funcChannel
    callback(32) ///< "Print 32" is the output
}

/// This goroutine sends a function into the channel 
func support(channel chan func(int32)) {
    channel <- sendingFunction
}

/// This func simply print the given integer
func sendingFunction(a int32) {
    fmt.Println("Print", a)
}
\end{lstlisting}
Truly this is not the most powerful feature of Go channels, the possibility to
send user-coded objects (as seen in barber's shop example) is even powerful, 
data structures are aggregate of fields and methods so within a single object 
passing we send a collection of behaviuors and states. 

\section{Conclusions}
% FIXME sistemare le conclusioni non vanno bene
While talking about programming languages is hard not to fall on comparison, 
usally programmers learning a new language always ask: ``Does it looks like 
any other language?''. This time is really tought to say if Go really looks like
anything else. Language designer claimed that they took inspiration from C 
(that's obvious since Ken Thompson is in the team) and Python but there is 
really a lot inside here to simplify it as a mesh-up of those two languages. 
If we want to compare the concurrent part of the language we should look at Ada. 
While concurrency in Ada is far more structured and complicated than in Go it 
is really the only comparison we may do, other concurrent language does not 
have imperative structure (like Scala or Erlang) and they are generally 
relegated to niche applications. The great stuff about Go is that it is 
really simple, all his features are both powerful and easy.

\begin{thebibliography}{9}


\bibitem{hoare01}
    Hoare, C. A. R.
    \emph{Communicating sequential processes}.
    Communications of the ACM, 21(8): 666-677
    1978.

\bibitem{hoare02}
    Brookes, Stephen; C. A. R. Hoare and A. W. Roscoe.
    \emph{A Theory of Communicating Sequential Processes}. 
    Journal of the ACM 31 (3): 560-599
    1984.
    
\bibitem{roscoe01}
    Roscoe, A. W. 
    \emph{The Theory and Practice of Concurrency}. 
    Prentice Hall
    1997.

\bibitem{milner01}
    Milner R. 
   \emph{A Calculus of Communicating Systems}. 
    Springer Verlag
    1980.

\bibitem{dijkstra01}
    Dijkstra E. W.
    \emph{Cooperating Sequential Process}.
    Reprinted in \emph{Programming Languages} by F. Genyus,
    Academic Press, New York
    1965.

\bibitem{milner99}
    Milner R.
    \emph{Communicating and Mobile Systems: The $\pi$-calculus}.
    UK: Cambridge University Press
    1999.

\bibitem{gospec}
    R. Griesemer, R. Pike, K. Thompson.
    \emph{The Go Programming Language Specification}.
    \url{http://golang.org/doc/go_spec.html}

\end{thebibliography}


\end{document}
